Runtime Complexity (innermost) proof of /tmp/tmpQBBOuX/jwcime1.xml

The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(O(1), O(n^1)).

0 CpxTRS

↳1 CpxTrsToCdtProof (BOTH BOUNDS(ID, ID), 0 ms)

↳2 CdtProblem

    ↳3 CdtNarrowingProof (BOTH BOUNDS(ID, ID), 0 ms)

    ↳4 CdtProblem

    ↳5 CdtLeafRemovalProof (BOTH BOUNDS(ID, ID), 0 ms)

    ↳6 CdtProblem

    ↳7 CdtNarrowingProof (BOTH BOUNDS(ID, ID), 27 ms)

    ↳8 CdtProblem

    ↳9 CdtNarrowingProof (BOTH BOUNDS(ID, ID), 0 ms)

    ↳10 CdtProblem

    ↳11 CdtRewritingProof (BOTH BOUNDS(ID, ID), 4 ms)

    ↳12 CdtProblem

    ↳13 CdtRewritingProof (BOTH BOUNDS(ID, ID), 0 ms)

    ↳14 CdtProblem

    ↳15 CdtRewritingProof (BOTH BOUNDS(ID, ID), 0 ms)

    ↳16 CdtProblem

↳17 CpxTrsMatchBoundsTAProof (⇔, 0 ms)

↳18 BOUNDS(O(1), O(n^1))

(0) Obligation:

Runtime Complexity TRS:
The TRS R consists of the following rules:

f(x, f(y, a)) → f(f(f(f(a, x), y), a), h(a))

Rewrite Strategy: INNERMOST

(1) CpxTrsToCdtProof (BOTH BOUNDS(ID, ID) transformation)

Converted CpxTRS to CDT

(2) Obligation:

Complexity Dependency Tuples Problem
Rules:

f(z0, f(z1, a)) → f(f(f(f(a, z0), z1), a), h(a))

Tuples:

F(z0, f(z1, a)) → c(F(f(f(f(a, z0), z1), a), h(a)), F(f(f(a, z0), z1), a), F(f(a, z0), z1), F(a, z0))

S tuples:

F(z0, f(z1, a)) → c(F(f(f(f(a, z0), z1), a), h(a)), F(f(f(a, z0), z1), a), F(f(a, z0), z1), F(a, z0))

K tuples:none
Defined Rule Symbols:

f

Defined Pair Symbols:

F

Compound Symbols:

c

(3) CdtNarrowingProof (BOTH BOUNDS(ID, ID) transformation)

Use narrowing to replace F(z0, f(z1, a)) → c(F(f(f(f(a, z0), z1), a), h(a)), F(f(f(a, z0), z1), a), F(f(a, z0), z1), F(a, z0)) by

F(x0, f(f(z1, a), a)) → c(F(f(f(f(f(f(a, f(a, x0)), z1), a), h(a)), a), h(a)), F(f(f(a, x0), f(z1, a)), a), F(f(a, x0), f(z1, a)), F(a, x0))
F(f(z1, a), f(x1, a)) → c(F(f(f(f(f(f(f(a, a), z1), a), h(a)), x1), a), h(a)), F(f(f(a, f(z1, a)), x1), a), F(f(a, f(z1, a)), x1), F(a, f(z1, a)))
F(x0, f(x1, a)) → c

(4) Obligation:

Complexity Dependency Tuples Problem
Rules:

f(z0, f(z1, a)) → f(f(f(f(a, z0), z1), a), h(a))

Tuples:

F(x0, f(f(z1, a), a)) → c(F(f(f(f(f(f(a, f(a, x0)), z1), a), h(a)), a), h(a)), F(f(f(a, x0), f(z1, a)), a), F(f(a, x0), f(z1, a)), F(a, x0))
F(f(z1, a), f(x1, a)) → c(F(f(f(f(f(f(f(a, a), z1), a), h(a)), x1), a), h(a)), F(f(f(a, f(z1, a)), x1), a), F(f(a, f(z1, a)), x1), F(a, f(z1, a)))
F(x0, f(x1, a)) → c

S tuples:

F(x0, f(f(z1, a), a)) → c(F(f(f(f(f(f(a, f(a, x0)), z1), a), h(a)), a), h(a)), F(f(f(a, x0), f(z1, a)), a), F(f(a, x0), f(z1, a)), F(a, x0))
F(f(z1, a), f(x1, a)) → c(F(f(f(f(f(f(f(a, a), z1), a), h(a)), x1), a), h(a)), F(f(f(a, f(z1, a)), x1), a), F(f(a, f(z1, a)), x1), F(a, f(z1, a)))
F(x0, f(x1, a)) → c

K tuples:none
Defined Rule Symbols:

f

Defined Pair Symbols:

F

Compound Symbols:

c, c

(5) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID) transformation)

Removed 1 trailing nodes:

F(x0, f(x1, a)) → c

(6) Obligation:

Complexity Dependency Tuples Problem
Rules:

f(z0, f(z1, a)) → f(f(f(f(a, z0), z1), a), h(a))

Tuples:

F(x0, f(f(z1, a), a)) → c(F(f(f(f(f(f(a, f(a, x0)), z1), a), h(a)), a), h(a)), F(f(f(a, x0), f(z1, a)), a), F(f(a, x0), f(z1, a)), F(a, x0))
F(f(z1, a), f(x1, a)) → c(F(f(f(f(f(f(f(a, a), z1), a), h(a)), x1), a), h(a)), F(f(f(a, f(z1, a)), x1), a), F(f(a, f(z1, a)), x1), F(a, f(z1, a)))

S tuples:

F(x0, f(f(z1, a), a)) → c(F(f(f(f(f(f(a, f(a, x0)), z1), a), h(a)), a), h(a)), F(f(f(a, x0), f(z1, a)), a), F(f(a, x0), f(z1, a)), F(a, x0))
F(f(z1, a), f(x1, a)) → c(F(f(f(f(f(f(f(a, a), z1), a), h(a)), x1), a), h(a)), F(f(f(a, f(z1, a)), x1), a), F(f(a, f(z1, a)), x1), F(a, f(z1, a)))

K tuples:none
Defined Rule Symbols:

f

Defined Pair Symbols:

F

Compound Symbols:

c

(7) CdtNarrowingProof (BOTH BOUNDS(ID, ID) transformation)

Use narrowing to replace F(x0, f(f(z1, a), a)) → c(F(f(f(f(f(f(a, f(a, x0)), z1), a), h(a)), a), h(a)), F(f(f(a, x0), f(z1, a)), a), F(f(a, x0), f(z1, a)), F(a, x0)) by

F(x0, f(f(f(z1, a), a), a)) → c(F(f(f(f(f(f(f(f(a, f(a, f(a, x0))), z1), a), h(a)), a), h(a)), a), h(a)), F(f(f(a, x0), f(f(z1, a), a)), a), F(f(a, x0), f(f(z1, a), a)), F(a, x0))
F(a, f(f(x1, a), a)) → c(F(f(f(f(f(f(f(f(f(a, a), a), a), h(a)), x1), a), h(a)), a), h(a)), F(f(f(a, a), f(x1, a)), a), F(f(a, a), f(x1, a)), F(a, a))
F(f(z1, a), f(f(x1, a), a)) → c(F(f(f(f(f(f(a, f(f(f(f(a, a), z1), a), h(a))), x1), a), h(a)), a), h(a)), F(f(f(a, f(z1, a)), f(x1, a)), a), F(f(a, f(z1, a)), f(x1, a)), F(a, f(z1, a)))
F(x0, f(f(x1, a), a)) → c(F(f(f(a, x0), f(x1, a)), a), F(f(a, x0), f(x1, a)))

(8) Obligation:

Complexity Dependency Tuples Problem
Rules:

f(z0, f(z1, a)) → f(f(f(f(a, z0), z1), a), h(a))

Tuples:

F(f(z1, a), f(x1, a)) → c(F(f(f(f(f(f(f(a, a), z1), a), h(a)), x1), a), h(a)), F(f(f(a, f(z1, a)), x1), a), F(f(a, f(z1, a)), x1), F(a, f(z1, a)))
F(x0, f(f(f(z1, a), a), a)) → c(F(f(f(f(f(f(f(f(a, f(a, f(a, x0))), z1), a), h(a)), a), h(a)), a), h(a)), F(f(f(a, x0), f(f(z1, a), a)), a), F(f(a, x0), f(f(z1, a), a)), F(a, x0))
F(a, f(f(x1, a), a)) → c(F(f(f(f(f(f(f(f(f(a, a), a), a), h(a)), x1), a), h(a)), a), h(a)), F(f(f(a, a), f(x1, a)), a), F(f(a, a), f(x1, a)), F(a, a))
F(f(z1, a), f(f(x1, a), a)) → c(F(f(f(f(f(f(a, f(f(f(f(a, a), z1), a), h(a))), x1), a), h(a)), a), h(a)), F(f(f(a, f(z1, a)), f(x1, a)), a), F(f(a, f(z1, a)), f(x1, a)), F(a, f(z1, a)))
F(x0, f(f(x1, a), a)) → c(F(f(f(a, x0), f(x1, a)), a), F(f(a, x0), f(x1, a)))

S tuples:

F(f(z1, a), f(x1, a)) → c(F(f(f(f(f(f(f(a, a), z1), a), h(a)), x1), a), h(a)), F(f(f(a, f(z1, a)), x1), a), F(f(a, f(z1, a)), x1), F(a, f(z1, a)))
F(x0, f(f(f(z1, a), a), a)) → c(F(f(f(f(f(f(f(f(a, f(a, f(a, x0))), z1), a), h(a)), a), h(a)), a), h(a)), F(f(f(a, x0), f(f(z1, a), a)), a), F(f(a, x0), f(f(z1, a), a)), F(a, x0))
F(a, f(f(x1, a), a)) → c(F(f(f(f(f(f(f(f(f(a, a), a), a), h(a)), x1), a), h(a)), a), h(a)), F(f(f(a, a), f(x1, a)), a), F(f(a, a), f(x1, a)), F(a, a))
F(f(z1, a), f(f(x1, a), a)) → c(F(f(f(f(f(f(a, f(f(f(f(a, a), z1), a), h(a))), x1), a), h(a)), a), h(a)), F(f(f(a, f(z1, a)), f(x1, a)), a), F(f(a, f(z1, a)), f(x1, a)), F(a, f(z1, a)))
F(x0, f(f(x1, a), a)) → c(F(f(f(a, x0), f(x1, a)), a), F(f(a, x0), f(x1, a)))

K tuples:none
Defined Rule Symbols:

f

Defined Pair Symbols:

F

Compound Symbols:

c, c

(9) CdtNarrowingProof (BOTH BOUNDS(ID, ID) transformation)

Use narrowing to replace F(f(z1, a), f(x1, a)) → c(F(f(f(f(f(f(f(a, a), z1), a), h(a)), x1), a), h(a)), F(f(f(a, f(z1, a)), x1), a), F(f(a, f(z1, a)), x1), F(a, f(z1, a))) by

F(f(x0, a), f(f(z1, a), a)) → c(F(f(f(f(f(f(a, f(f(f(f(a, a), x0), a), h(a))), z1), a), h(a)), a), h(a)), F(f(f(a, f(x0, a)), f(z1, a)), a), F(f(a, f(x0, a)), f(z1, a)), F(a, f(x0, a)))
F(f(f(z1, a), a), f(x1, a)) → c(F(f(f(f(f(f(f(f(f(a, f(a, a)), z1), a), h(a)), a), h(a)), x1), a), h(a)), F(f(f(a, f(f(z1, a), a)), x1), a), F(f(a, f(f(z1, a), a)), x1), F(a, f(f(z1, a), a)))
F(f(x0, a), f(x1, a)) → c(F(f(f(a, f(x0, a)), x1), a), F(f(a, f(x0, a)), x1), F(a, f(x0, a)))

(10) Obligation:

Complexity Dependency Tuples Problem
Rules:

f(z0, f(z1, a)) → f(f(f(f(a, z0), z1), a), h(a))

Tuples:

F(x0, f(f(f(z1, a), a), a)) → c(F(f(f(f(f(f(f(f(a, f(a, f(a, x0))), z1), a), h(a)), a), h(a)), a), h(a)), F(f(f(a, x0), f(f(z1, a), a)), a), F(f(a, x0), f(f(z1, a), a)), F(a, x0))
F(a, f(f(x1, a), a)) → c(F(f(f(f(f(f(f(f(f(a, a), a), a), h(a)), x1), a), h(a)), a), h(a)), F(f(f(a, a), f(x1, a)), a), F(f(a, a), f(x1, a)), F(a, a))
F(f(z1, a), f(f(x1, a), a)) → c(F(f(f(f(f(f(a, f(f(f(f(a, a), z1), a), h(a))), x1), a), h(a)), a), h(a)), F(f(f(a, f(z1, a)), f(x1, a)), a), F(f(a, f(z1, a)), f(x1, a)), F(a, f(z1, a)))
F(x0, f(f(x1, a), a)) → c(F(f(f(a, x0), f(x1, a)), a), F(f(a, x0), f(x1, a)))
F(f(f(z1, a), a), f(x1, a)) → c(F(f(f(f(f(f(f(f(f(a, f(a, a)), z1), a), h(a)), a), h(a)), x1), a), h(a)), F(f(f(a, f(f(z1, a), a)), x1), a), F(f(a, f(f(z1, a), a)), x1), F(a, f(f(z1, a), a)))
F(f(x0, a), f(x1, a)) → c(F(f(f(a, f(x0, a)), x1), a), F(f(a, f(x0, a)), x1), F(a, f(x0, a)))

S tuples:

F(x0, f(f(f(z1, a), a), a)) → c(F(f(f(f(f(f(f(f(a, f(a, f(a, x0))), z1), a), h(a)), a), h(a)), a), h(a)), F(f(f(a, x0), f(f(z1, a), a)), a), F(f(a, x0), f(f(z1, a), a)), F(a, x0))
F(a, f(f(x1, a), a)) → c(F(f(f(f(f(f(f(f(f(a, a), a), a), h(a)), x1), a), h(a)), a), h(a)), F(f(f(a, a), f(x1, a)), a), F(f(a, a), f(x1, a)), F(a, a))
F(f(z1, a), f(f(x1, a), a)) → c(F(f(f(f(f(f(a, f(f(f(f(a, a), z1), a), h(a))), x1), a), h(a)), a), h(a)), F(f(f(a, f(z1, a)), f(x1, a)), a), F(f(a, f(z1, a)), f(x1, a)), F(a, f(z1, a)))
F(x0, f(f(x1, a), a)) → c(F(f(f(a, x0), f(x1, a)), a), F(f(a, x0), f(x1, a)))
F(f(f(z1, a), a), f(x1, a)) → c(F(f(f(f(f(f(f(f(f(a, f(a, a)), z1), a), h(a)), a), h(a)), x1), a), h(a)), F(f(f(a, f(f(z1, a), a)), x1), a), F(f(a, f(f(z1, a), a)), x1), F(a, f(f(z1, a), a)))
F(f(x0, a), f(x1, a)) → c(F(f(f(a, f(x0, a)), x1), a), F(f(a, f(x0, a)), x1), F(a, f(x0, a)))

K tuples:none
Defined Rule Symbols:

f

Defined Pair Symbols:

F

Compound Symbols:

c, c, c

(11) CdtRewritingProof (BOTH BOUNDS(ID, ID) transformation)

Used rewriting to replace F(x0, f(f(f(z1, a), a), a)) → c(F(f(f(f(f(f(f(f(a, f(a, f(a, x0))), z1), a), h(a)), a), h(a)), a), h(a)), F(f(f(a, x0), f(f(z1, a), a)), a), F(f(a, x0), f(f(z1, a), a)), F(a, x0)) by F(z0, f(f(f(z1, a), a), a)) → c(F(f(f(f(f(f(f(f(a, f(a, f(a, z0))), z1), a), h(a)), a), h(a)), a), h(a)), F(f(f(f(f(a, f(a, z0)), f(z1, a)), a), h(a)), a), F(f(a, z0), f(f(z1, a), a)), F(a, z0))

(12) Obligation:

Complexity Dependency Tuples Problem
Rules:

f(z0, f(z1, a)) → f(f(f(f(a, z0), z1), a), h(a))

Tuples:

F(a, f(f(x1, a), a)) → c(F(f(f(f(f(f(f(f(f(a, a), a), a), h(a)), x1), a), h(a)), a), h(a)), F(f(f(a, a), f(x1, a)), a), F(f(a, a), f(x1, a)), F(a, a))
F(f(z1, a), f(f(x1, a), a)) → c(F(f(f(f(f(f(a, f(f(f(f(a, a), z1), a), h(a))), x1), a), h(a)), a), h(a)), F(f(f(a, f(z1, a)), f(x1, a)), a), F(f(a, f(z1, a)), f(x1, a)), F(a, f(z1, a)))
F(x0, f(f(x1, a), a)) → c(F(f(f(a, x0), f(x1, a)), a), F(f(a, x0), f(x1, a)))
F(f(f(z1, a), a), f(x1, a)) → c(F(f(f(f(f(f(f(f(f(a, f(a, a)), z1), a), h(a)), a), h(a)), x1), a), h(a)), F(f(f(a, f(f(z1, a), a)), x1), a), F(f(a, f(f(z1, a), a)), x1), F(a, f(f(z1, a), a)))
F(f(x0, a), f(x1, a)) → c(F(f(f(a, f(x0, a)), x1), a), F(f(a, f(x0, a)), x1), F(a, f(x0, a)))
F(z0, f(f(f(z1, a), a), a)) → c(F(f(f(f(f(f(f(f(a, f(a, f(a, z0))), z1), a), h(a)), a), h(a)), a), h(a)), F(f(f(f(f(a, f(a, z0)), f(z1, a)), a), h(a)), a), F(f(a, z0), f(f(z1, a), a)), F(a, z0))

S tuples:

F(a, f(f(x1, a), a)) → c(F(f(f(f(f(f(f(f(f(a, a), a), a), h(a)), x1), a), h(a)), a), h(a)), F(f(f(a, a), f(x1, a)), a), F(f(a, a), f(x1, a)), F(a, a))
F(f(z1, a), f(f(x1, a), a)) → c(F(f(f(f(f(f(a, f(f(f(f(a, a), z1), a), h(a))), x1), a), h(a)), a), h(a)), F(f(f(a, f(z1, a)), f(x1, a)), a), F(f(a, f(z1, a)), f(x1, a)), F(a, f(z1, a)))
F(x0, f(f(x1, a), a)) → c(F(f(f(a, x0), f(x1, a)), a), F(f(a, x0), f(x1, a)))
F(f(f(z1, a), a), f(x1, a)) → c(F(f(f(f(f(f(f(f(f(a, f(a, a)), z1), a), h(a)), a), h(a)), x1), a), h(a)), F(f(f(a, f(f(z1, a), a)), x1), a), F(f(a, f(f(z1, a), a)), x1), F(a, f(f(z1, a), a)))
F(f(x0, a), f(x1, a)) → c(F(f(f(a, f(x0, a)), x1), a), F(f(a, f(x0, a)), x1), F(a, f(x0, a)))
F(z0, f(f(f(z1, a), a), a)) → c(F(f(f(f(f(f(f(f(a, f(a, f(a, z0))), z1), a), h(a)), a), h(a)), a), h(a)), F(f(f(f(f(a, f(a, z0)), f(z1, a)), a), h(a)), a), F(f(a, z0), f(f(z1, a), a)), F(a, z0))

K tuples:none
Defined Rule Symbols:

f

Defined Pair Symbols:

F

Compound Symbols:

c, c, c

(13) CdtRewritingProof (BOTH BOUNDS(ID, ID) transformation)

Used rewriting to replace F(a, f(f(x1, a), a)) → c(F(f(f(f(f(f(f(f(f(a, a), a), a), h(a)), x1), a), h(a)), a), h(a)), F(f(f(a, a), f(x1, a)), a), F(f(a, a), f(x1, a)), F(a, a)) by F(a, f(f(z0, a), a)) → c(F(f(f(f(f(f(f(f(f(a, a), a), a), h(a)), z0), a), h(a)), a), h(a)), F(f(f(f(f(a, f(a, a)), z0), a), h(a)), a), F(f(a, a), f(z0, a)), F(a, a))

(14) Obligation:

Complexity Dependency Tuples Problem
Rules:

f(z0, f(z1, a)) → f(f(f(f(a, z0), z1), a), h(a))

Tuples:

F(f(z1, a), f(f(x1, a), a)) → c(F(f(f(f(f(f(a, f(f(f(f(a, a), z1), a), h(a))), x1), a), h(a)), a), h(a)), F(f(f(a, f(z1, a)), f(x1, a)), a), F(f(a, f(z1, a)), f(x1, a)), F(a, f(z1, a)))
F(x0, f(f(x1, a), a)) → c(F(f(f(a, x0), f(x1, a)), a), F(f(a, x0), f(x1, a)))
F(f(f(z1, a), a), f(x1, a)) → c(F(f(f(f(f(f(f(f(f(a, f(a, a)), z1), a), h(a)), a), h(a)), x1), a), h(a)), F(f(f(a, f(f(z1, a), a)), x1), a), F(f(a, f(f(z1, a), a)), x1), F(a, f(f(z1, a), a)))
F(f(x0, a), f(x1, a)) → c(F(f(f(a, f(x0, a)), x1), a), F(f(a, f(x0, a)), x1), F(a, f(x0, a)))
F(z0, f(f(f(z1, a), a), a)) → c(F(f(f(f(f(f(f(f(a, f(a, f(a, z0))), z1), a), h(a)), a), h(a)), a), h(a)), F(f(f(f(f(a, f(a, z0)), f(z1, a)), a), h(a)), a), F(f(a, z0), f(f(z1, a), a)), F(a, z0))
F(a, f(f(z0, a), a)) → c(F(f(f(f(f(f(f(f(f(a, a), a), a), h(a)), z0), a), h(a)), a), h(a)), F(f(f(f(f(a, f(a, a)), z0), a), h(a)), a), F(f(a, a), f(z0, a)), F(a, a))

S tuples:

F(f(z1, a), f(f(x1, a), a)) → c(F(f(f(f(f(f(a, f(f(f(f(a, a), z1), a), h(a))), x1), a), h(a)), a), h(a)), F(f(f(a, f(z1, a)), f(x1, a)), a), F(f(a, f(z1, a)), f(x1, a)), F(a, f(z1, a)))
F(x0, f(f(x1, a), a)) → c(F(f(f(a, x0), f(x1, a)), a), F(f(a, x0), f(x1, a)))
F(f(f(z1, a), a), f(x1, a)) → c(F(f(f(f(f(f(f(f(f(a, f(a, a)), z1), a), h(a)), a), h(a)), x1), a), h(a)), F(f(f(a, f(f(z1, a), a)), x1), a), F(f(a, f(f(z1, a), a)), x1), F(a, f(f(z1, a), a)))
F(f(x0, a), f(x1, a)) → c(F(f(f(a, f(x0, a)), x1), a), F(f(a, f(x0, a)), x1), F(a, f(x0, a)))
F(z0, f(f(f(z1, a), a), a)) → c(F(f(f(f(f(f(f(f(a, f(a, f(a, z0))), z1), a), h(a)), a), h(a)), a), h(a)), F(f(f(f(f(a, f(a, z0)), f(z1, a)), a), h(a)), a), F(f(a, z0), f(f(z1, a), a)), F(a, z0))
F(a, f(f(z0, a), a)) → c(F(f(f(f(f(f(f(f(f(a, a), a), a), h(a)), z0), a), h(a)), a), h(a)), F(f(f(f(f(a, f(a, a)), z0), a), h(a)), a), F(f(a, a), f(z0, a)), F(a, a))

K tuples:none
Defined Rule Symbols:

f

Defined Pair Symbols:

F

Compound Symbols:

c, c, c

(15) CdtRewritingProof (BOTH BOUNDS(ID, ID) transformation)

Used rewriting to replace F(f(z1, a), f(f(x1, a), a)) → c(F(f(f(f(f(f(a, f(f(f(f(a, a), z1), a), h(a))), x1), a), h(a)), a), h(a)), F(f(f(a, f(z1, a)), f(x1, a)), a), F(f(a, f(z1, a)), f(x1, a)), F(a, f(z1, a))) by F(f(z0, a), f(f(z1, a), a)) → c(F(f(f(f(f(f(a, f(f(f(f(a, a), z0), a), h(a))), z1), a), h(a)), a), h(a)), F(f(f(a, f(z0, a)), f(z1, a)), a), F(f(f(f(f(a, a), z0), a), h(a)), f(z1, a)), F(a, f(z0, a)))

(16) Obligation:

Complexity Dependency Tuples Problem
Rules:

f(z0, f(z1, a)) → f(f(f(f(a, z0), z1), a), h(a))

Tuples:

F(f(z1, a), f(f(x1, a), a)) → c(F(f(f(f(f(f(a, f(f(f(f(a, a), z1), a), h(a))), x1), a), h(a)), a), h(a)), F(f(f(a, f(z1, a)), f(x1, a)), a), F(f(a, f(z1, a)), f(x1, a)), F(a, f(z1, a)))
F(x0, f(f(x1, a), a)) → c(F(f(f(a, x0), f(x1, a)), a), F(f(a, x0), f(x1, a)))
F(f(f(z1, a), a), f(x1, a)) → c(F(f(f(f(f(f(f(f(f(a, f(a, a)), z1), a), h(a)), a), h(a)), x1), a), h(a)), F(f(f(a, f(f(z1, a), a)), x1), a), F(f(a, f(f(z1, a), a)), x1), F(a, f(f(z1, a), a)))
F(f(x0, a), f(x1, a)) → c(F(f(f(a, f(x0, a)), x1), a), F(f(a, f(x0, a)), x1), F(a, f(x0, a)))
F(z0, f(f(f(z1, a), a), a)) → c(F(f(f(f(f(f(f(f(a, f(a, f(a, z0))), z1), a), h(a)), a), h(a)), a), h(a)), F(f(f(f(f(a, f(a, z0)), f(z1, a)), a), h(a)), a), F(f(a, z0), f(f(z1, a), a)), F(a, z0))
F(a, f(f(z0, a), a)) → c(F(f(f(f(f(f(f(f(f(a, a), a), a), h(a)), z0), a), h(a)), a), h(a)), F(f(f(f(f(a, f(a, a)), z0), a), h(a)), a), F(f(a, a), f(z0, a)), F(a, a))
F(f(z0, a), f(f(z1, a), a)) → c(F(f(f(f(f(f(a, f(f(f(f(a, a), z0), a), h(a))), z1), a), h(a)), a), h(a)), F(f(f(a, f(z0, a)), f(z1, a)), a), F(f(f(f(f(a, a), z0), a), h(a)), f(z1, a)), F(a, f(z0, a)))

S tuples:

F(x0, f(f(x1, a), a)) → c(F(f(f(a, x0), f(x1, a)), a), F(f(a, x0), f(x1, a)))
F(f(f(z1, a), a), f(x1, a)) → c(F(f(f(f(f(f(f(f(f(a, f(a, a)), z1), a), h(a)), a), h(a)), x1), a), h(a)), F(f(f(a, f(f(z1, a), a)), x1), a), F(f(a, f(f(z1, a), a)), x1), F(a, f(f(z1, a), a)))
F(f(x0, a), f(x1, a)) → c(F(f(f(a, f(x0, a)), x1), a), F(f(a, f(x0, a)), x1), F(a, f(x0, a)))
F(z0, f(f(f(z1, a), a), a)) → c(F(f(f(f(f(f(f(f(a, f(a, f(a, z0))), z1), a), h(a)), a), h(a)), a), h(a)), F(f(f(f(f(a, f(a, z0)), f(z1, a)), a), h(a)), a), F(f(a, z0), f(f(z1, a), a)), F(a, z0))
F(a, f(f(z0, a), a)) → c(F(f(f(f(f(f(f(f(f(a, a), a), a), h(a)), z0), a), h(a)), a), h(a)), F(f(f(f(f(a, f(a, a)), z0), a), h(a)), a), F(f(a, a), f(z0, a)), F(a, a))
F(f(z0, a), f(f(z1, a), a)) → c(F(f(f(f(f(f(a, f(f(f(f(a, a), z0), a), h(a))), z1), a), h(a)), a), h(a)), F(f(f(a, f(z0, a)), f(z1, a)), a), F(f(f(f(f(a, a), z0), a), h(a)), f(z1, a)), F(a, f(z0, a)))

K tuples:none
Defined Rule Symbols:

f

Defined Pair Symbols:

F

Compound Symbols:

c, c, c

(17) CpxTrsMatchBoundsTAProof (EQUIVALENT transformation)

A linear upper bound on the runtime complexity of the TRS R could be shown with a Match-Bound[TAB_LEFTLINEAR,TAB_NONLEFTLINEAR] (for contructor-based start-terms) of 0.

The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by:
final states : [1]
transitions:
a0() → 0
h0(0) → 0
f0(0, 0) → 1

(0) Obligation:

(1) CpxTrsToCdtProof (BOTH BOUNDS(ID, ID) transformation)

(2) Obligation:

(3) CdtNarrowingProof (BOTH BOUNDS(ID, ID) transformation)

(4) Obligation:

(5) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID) transformation)

(6) Obligation:

(7) CdtNarrowingProof (BOTH BOUNDS(ID, ID) transformation)

(8) Obligation:

(9) CdtNarrowingProof (BOTH BOUNDS(ID, ID) transformation)

(10) Obligation:

(11) CdtRewritingProof (BOTH BOUNDS(ID, ID) transformation)

(12) Obligation:

(13) CdtRewritingProof (BOTH BOUNDS(ID, ID) transformation)

(14) Obligation:

(15) CdtRewritingProof (BOTH BOUNDS(ID, ID) transformation)

(16) Obligation:

(17) CpxTrsMatchBoundsTAProof (EQUIVALENT transformation)

(18) BOUNDS(O(1), O(n^1))